The present invention relates to a method and to an apparatus for transferring information through a communication medium. More particularly, the present invention relates to a method and to an apparatus for scheduling the transmission of information across connections in a communication system.
Various systems have been adopted to carry digitally-encoded signals for communication applications, such as, telephone, video, and data services. These systems are often connection-oriented packet mode transmission systems, such as, asynchronous transfer mode (ATM) systems, frame relay systems, X.25 systems, or other transmission systems. Connection-oriented systems (e.g., ATM systems) have been employed in private and public communication systems or networks (e.g., wide area networks (WANs)) to transfer packetized signals (e.g., data cells or protocol data units) across communication lines, such as, telephone lines, cables, optical fibers, air waves, satellite links, or other communication media.
As an example, the ATM system transfers the data cells or units across the ATM system via connections or channels. The data cells can represent voice, sound, video, graphics, data, or combinations thereof for use in computing or communication applications. The connections can be part of a single physical link carrying a number of logical connections or be a single isolated path. The connections are often classified as either virtual channel connections (VCC), or virtual path connections (VPC) and either permanent virtual connections (PVC), or switched virtual connections (SVC). Connections are generally defined by a source and a destination for the data cell.
ATM systems or networks are generally utilized to support the integration of high quality voice, video, and high speed data traffic which can have specific conformance and quality of service (QOS) requirements. A scheduler is employed to properly select connections for transmission in accordance with operational parameters, such as, QOS requirements. The scheduler organizes transmission of data cells associated with the connections to guarantee QOS requirements and protocol conformance at the network ingress point as well as to maximize bandwidth for the communication system.
ATM systems can utilize at least four types of service categories or modes of traffic for transmission of data cells on connections. These four types include the constant bit rate (CBR) mode, the variable bit rate (VBR) mode, the unspecified bit rate (UBR) mode, and the available bit rate (ABR) mode. Each of these modes have somewhat different transmission protocol requirements. For example, the CBR mode requires that a connection be able to send a specific number of cells or bits per second; the CBR mode must have a set end-to-end bandwidth. The CBR mode is often utilized for data sources, such as, voice or video circuits which are susceptible to cell delay variations (CDV). The VBR mode often utilizes a xe2x80x9csingle leaky bucketxe2x80x9d algorithm (e.g., virtual scheduling algorithm) or xe2x80x9cdual leaky bucketxe2x80x9d algorithm. Although the VBR mode has somewhat more flexible timing requirements than the CBR mode, the VBR mode must meet timing requirements dictated by the single or dual bucket algorithms. The ABR mode requires the sending of data cells in response to feedback from the network.
To appropriately supply and maximize the effectiveness of the transmission of the CBR, UBR, ABR, and VBR modes of traffic on the network, a scheduler controls a segmentation coprocessor (e.g., segmentation and reassembly unit) to direct communication of data cells or data protocol units on the connections. Generally, the scheduler attempts to select particular connections for transmission at particular times to guarantee conformance to traffic contracts and to QOS at network ingress points. This selection process, or scheduling, selects various connections for transmission based upon operational parameters associated with each connection, with feedback from the network, and with traffic mode timing requirements.
Scheduling a large number of connections with particular timing and communication criteria can lead to complex scheduling problems. For example, various connections can need a particular capacity from the network, and the availability of the particular capacity can be impinged by congestion across the network. These scheduling problems can be compounded by the specific requirements of CBR mode, VBR mode, UBR mode, and ABR modes of traffic.
Traditional network scheduling algorithms, such as, Token Ring and Ethernet utilize fairly simplified scheduling algorithms. The algorithms are typically based upon transmission schemes wherein each member of the network gets a fair share of the network bandwidth. These systems cannot handle QOS requirements or the four categories (e.g., CBR mode, VBR mode, UBR mode, and ABR mode) of traffic for ATM systems.
Prior schedulers utilized in ATM systems access a fixed size schedule table to assist time scheduling of connections. The fixed schedule table is comprised of slots, each of which is assigned to particular connections. The scheduler processes each slot one-by-one and transmits the connection assigned to the slot being processed to the network. These prior schedulers are somewhat inflexible and prioritize CBR and VBR modes traffic. Further, the fixed schedule table requires that the CBR modes of traffic be sent a fixed rate or a harmonic of a fixed rate. Further still, these prior schedulers often must send idle cells to maintain the drain rate for the connection.
Other prior schedulers utilize a first-in, first-out (FIFO) memory and a timer (e.g., hardware units) to appropriately send connections across the network. However, the number of hardware units is limited by circuit size design criteria and cannot be dynamically allocated as bandwidth becomes available. Each FIFO and timer must be dedicated to a particular rate of transmission. Therefore, the rates of transmission are limited. Additionally, these prior schedulers cannot prioritize VBR and CBR modes of traffic.
U.S. patent application Ser. No. 08/759,057 filed Dec. 2, 1996, by Lincoln, entitled xe2x80x9cScheduler Utilizing Dynamic Schedule Tablexe2x80x9d discloses a communication system which dynamically manages and prioritizes modes of traffic. The communication system can be arranged as an asynchronous transfer mode (ATM) system which can efficiently handle the CBR mode of traffic, the VBR mode of traffic, the UBR mode of traffic, and the ABR mode of traffic. Further, both the CBR mode of traffic and the VBR mode of traffic can be handled on a dynamic basis.
Conventional schedulers do not simultaneously support different quality of service connections (e.g., UBR, VBR, ABR) in a tunnel mode. For example, a tunnel mode is utilized to share a portion of the fixed maximum bandwidth among a number of connections. xe2x80x9cTunnellingxe2x80x9d underneath the fixed maximum bandwidth is achieved by assigning an arbitrary maximum bandwidth to a group of connections each of which has an individual service contract. This feature allows users or customers to advantageously create a network overlying the service providers (e.g., telephone companies) network).
Conventional systems only allow UBR connections to utilize a tunnel mode and generally can only support a single tunnel. UBR connections cannot flexibly absorb excess bandwidth and must be processed in a round-robin fashion. Further, conventional systems are not capable of simultaneously supporting different service connections within a fixed bandwidth pipe (tunnel) where the connections are of different service classes and are not capable of supporting multiple tunnel modes.
Thus, there is a need for a scheduler which can simultaneously support different service connections of different service classes within a fixed bandwidth pipe (tunnel). Additionally, there is a need for a scheduler which can support multiple tunnels. Further, there is a need for a schedular which can simultaneously shape individual service classes within a fixed bandwidth pipe or tunnel.
The present invention relates to a traffic manager system coupled to a communication system for scheduling transmission of data associated with a plurality of connections in the communication system. The traffic manager includes a schedule table, a global priority queue, and a scheduler. The schedule table includes a plurality of slot locations, each having a plurality of tunnel entries. The scheduler is coupled to the schedule table and the global priority queue. The global priority queue has a tunnel level associated with the plurality of tunnel entries of the slot. The scheduler processes the slot locations in the schedule table and sets a tunnel active in response to processing one of the plurality of tunnel entries. The scheduler selects at least one connection from the at least one tunnel level when active, which thus provides for the selection of connections from a plurality of service classes. As such, the scheduler allows per connection shaping in the tunnel mode. The scheduler, thus, maximizes communication bandwidth.
The present invention further relates to a traffic manager system coupled to a communication system for scheduling transmission of data associated with a plurality of connections in the communication system. The traffic manager includes a schedule table, a global priority queue, and a scheduler. The schedule table includes a plurality of slot locations, each having at least one CBR entry. The scheduler is coupled to the schedule table and the global priority queue. The global priority queue has at least one tunnel level associated with the tunnel entry of the slot. The scheduler processes the CBR entry of the slot locations in the schedule table and sets a tunnel active in response to a no data available flag associated with a connection in the CBR entry.
The present invention still further relates to a communication system including a control memory means and a scheduler means. The control memory means defines a plurality of connections from a plurality of service classes. The scheduler means schedules the connections in accordance with a plurality of tunnel levels.
The present invention even further relates to a method of scheduling connections for transmission of data on a communication network. In the method, the scheduler accesses a plurality of tunnel entries in a schedule table and retrieves connection information associated with a plurality of tunnel connections. The scheduler places the connection information associated with the tunnel entries in a selected tunnel level of a plurality of tunnel levels. The scheduler processes the selected tunnel level to communicate information associated with the connection information.